'''
https://leetcode.cn/problems/check-completeness-of-a-binary-tree/description/
'''
from collections import deque
from typing import Optional

from c06_tree.utils import TreeNode


class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        # 层级遍历
        #   1 有右无左False
        #   2 当子节点不全时，后续的节点必须都是叶子节点
        flag = False
        q = deque([root])
        while q:
            level_size = len(q)
            for _ in range(level_size):
                node = q.popleft()
                if node.right and (not node.left): return False
                if flag and (node.left or node.right): return False
                flag = (not node.left) or (not node.right)
                if node.left: q.append(node.left)
                if node.right: q.append(node.right)
        return True
